﻿using System.Collections.Generic;
    //若索引从零开始，那么设父节点索引为 i 那么左子节点索引为i*2+1,右子节点索引为i*2+2
public delegate bool Comparer<T>(T lhs, T rhs);
public class Heap<T>
{
    List<T> dataList;
    public Comparer<T> Comparer;
    public int Count { get { return dataList.Count; } }
    public Heap(Comparer<T> comparer, int size = 8)
    {
        dataList = new List<T>(size);
        Comparer = comparer;
    }
    public T this[int idx]
    {
        get { return dataList[idx]; }
    }
    public void Add(T data)
    {
        dataList.Add(data);
        MoveUp(dataList.Count - 1);
    }
    /// <summary>
    /// 只添加而不更新堆
    /// </summary>
    public void AddWithNoHeap(T data)
    {
        dataList.Add(data);
    }
    /// <summary>
    /// 只移除而不更新堆
    /// </summary>
    public T RemoveTopWithNoHeap()
    {
        T res = dataList[0];
        dataList[0] = dataList[dataList.Count - 1];
        dataList.RemoveAt(dataList.Count - 1);
        return res;
    }
    public T RemoveTop()
    {
        T res = dataList[0];
        dataList[0] = dataList[dataList.Count - 1];
        dataList.RemoveAt(dataList.Count - 1);
        MoveDown(0);
        return res;
    }
    public void Clear()
    {
        dataList.Clear();
    }

    public void ReBuildHeap()
    {
        for (int i = dataList.Count / 2 - 1; i >= 0; i--)
            MoveDown(i);
    }

    public void MoveUp(int idx)
    {
        bool flag = true;
        while (idx > 0 && flag)
        {
            int swapidx = (idx - 1) / 2;
            if (Comparer(dataList[idx], dataList[swapidx]))
            {
                Swap(idx, swapidx);
                idx = swapidx;
            }
            else
                flag = false;
        }
    }
    void MoveDown(int idx)
    {
        bool flag = true;
        int leftidx = idx * 2 + 1;
        int rightidx = leftidx + 1;
        while (rightidx <= dataList.Count && flag)
        {
            int swapidx = 0;
            if (rightidx < dataList.Count)
                swapidx = Comparer(dataList[leftidx], dataList[rightidx]) ? leftidx : rightidx;
            else
                swapidx = leftidx;
            if (Comparer(dataList[swapidx], dataList[idx]))
            {
                Swap(idx, swapidx);
                idx = swapidx;
                leftidx = idx * 2 + 1;
                rightidx = leftidx + 1;
            }
            else
                flag = false;
        }
    }
    void Swap(int i, int j)
    {
        T temp = dataList[i];
        dataList[i] = dataList[j];
        dataList[j] = temp;
    }
}
